A branch instruction is an instruction that switches the system CPU (central processing unit) to another location in memory. A branch prediction is a prediction of the outcome of a branch instruction such that the system prefetches those instructions and executes them in parallel with the current instructions. If the prediction is wrong the system must waste processing cycles fetching the correct instruction.
The basic dataflow for an instruction is: instruction fetch, decode, cache access, execute, and result write back. Instructions enter the pipeline in program order. Any delay in instruction fetch adds latency and so hurts the performance.
Branch target prediction is employed in many processors to predict the target of an indirect branch. An indirect branch is a branch whose target is computed at run-time. A common example of an instruction sequence using an indirect branch is an instruction loading a register from a table, followed by the branch using the target stored in the register. Many high-level programming languages employ indirect branches. For example, in object-oriented languages such as Java, C++, and C#, indirect branches can be used for virtual function calls, where the target of a branch is obtained from a set of potential targets by examining the content of an object. Another example is the C/C++/Java switch statement, where the target could be obtained from a table indexed by the value in the statement. There is a need for predicting targets that may be employed in situations where a given branch has multiple targets, and/or subroutine returns and many branches with computed targets.